﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _16_ThreeSumClosest
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] nums = new int[] { 1, 1, 1, 0 };
            int result = ThreeSumClosest(nums, 100);
            Console.WriteLine(result);
            Console.ReadLine();
        }

        private static int ThreeSumClosest(int[] nums, int target)
        {
            Array.Sort(nums);

            int result = nums[0] + nums[1] + nums[nums.Length - 1];
            
            for (int i = 0; i < nums.Length - 2; i++)
            {
                int start = i + 1, end = nums.Length - 1;
                while (start < end)
                {
                    int sum = nums[i] + nums[start] + nums[end];
                    if (sum > target)
                    {
                        end--;
                    }
                    else
                    {
                        start++;
                    }
                    if (Math.Abs(sum - target) < Math.Abs(result - target))
                    {
                        result = sum;
                    }
                }
            }
            return result;
        }
    }
}
